// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
 *******************************************************************************
 *   Copyright (C) 2011-2014, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 *******************************************************************************
 *   created on: 2011jan05
 *   created by: Markus W. Scherer
 *   ported from ICU4C stringtriebuilder.h/.cpp
 */
package com.ibm.icu.util;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Base class for string trie builder classes.
 *
 * <p>This class is not intended for public subclassing.
 *
 * @author Markus W. Scherer
 * @stable ICU 4.8
 */
public abstract class StringTrieBuilder {
    /**
     * Build options for BytesTrieBuilder and CharsTrieBuilder.
     *
     * @stable ICU 4.8
     */
    public enum Option {
        /**
         * Builds a trie quickly.
         *
         * @stable ICU 4.8
         */
        FAST,
        /**
         * Builds a trie more slowly, attempting to generate a shorter but equivalent serialization.
         * This build option also uses more memory.
         *
         * <p>This option can be effective when many integer values are the same and string/byte
         * sequence suffixes can be shared. Runtime speed is not expected to improve.
         *
         * @stable ICU 4.8
         */
        SMALL
    }

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected StringTrieBuilder() {}

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected void addImpl(CharSequence s, int value) {
        if (state != State.ADDING) {
            // Cannot add elements after building.
            throw new IllegalStateException("Cannot add (string, value) pairs after build().");
        }
        if (s.length() > 0xffff) {
            // Too long: Limited by iterator internals, and by builder recursion depth.
            throw new IndexOutOfBoundsException("The maximum string length is 0xffff.");
        }
        if (root == null) {
            root = createSuffixNode(s, 0, value);
        } else {
            root = root.add(this, s, 0, value);
        }
    }

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected final void buildImpl(Option buildOption) {
        switch (state) {
            case ADDING:
                if (root == null) {
                    throw new IndexOutOfBoundsException("No (string, value) pairs were added.");
                }
                if (buildOption == Option.FAST) {
                    state = State.BUILDING_FAST;
                    // Building "fast" is somewhat faster (25..50% in some test)
                    // because it makes registerNode() return the input node
                    // rather than checking for duplicates.
                    // As a result, we sometimes write larger trie serializations.
                    //
                    // In either case we need to fix-up linear-match nodes (for their maximum
                    // length)
                    // and branch nodes (turning dynamic branch nodes into trees of
                    // runtime-equivalent nodes), but the HashMap/hashCode()/equals() are omitted
                    // for
                    // nodes other than final values.
                } else {
                    state = State.BUILDING_SMALL;
                }
                break;
            case BUILDING_FAST:
            case BUILDING_SMALL:
                // Building must have failed.
                throw new IllegalStateException("Builder failed and must be clear()ed.");
            case BUILT:
                return; // Nothing more to do.
        }
        // Implementation note:
        // We really build three versions of the trie.
        // The first is a fully dynamic trie, built successively by addImpl().
        // Then we call root.register() to turn it into a tree of nodes
        // which is 1:1 equivalent to the runtime data structure.
        // Finally, root.markRightEdgesFirst() and root.write() write that serialized form.
        root = root.register(this);
        root.markRightEdgesFirst(-1);
        root.write(this);
        state = State.BUILT;
    }

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected void clearImpl() {
        strings.setLength(0);
        nodes.clear();
        root = null;
        state = State.ADDING;
    }

    /**
     * Makes sure that there is only one unique node registered that is equivalent to newNode,
     * unless BUILDING_FAST.
     *
     * @param newNode Input node. The builder takes ownership.
     * @return newNode if it is the first of its kind, or an equivalent node if newNode is a
     *     duplicate.
     */
    private final Node registerNode(Node newNode) {
        if (state == State.BUILDING_FAST) {
            return newNode;
        }
        // BUILDING_SMALL
        Node oldNode = nodes.get(newNode);
        if (oldNode != null) {
            return oldNode;
        }
        // If put() returns a non-null value from an equivalent, previously
        // registered node, then get() failed to find that and we will leak newNode.
        oldNode = nodes.put(newNode, newNode);
        assert (oldNode == null);
        return newNode;
    }

    /**
     * Makes sure that there is only one unique FinalValueNode registered with this value. Avoids
     * creating a node if the value is a duplicate.
     *
     * @param value A final value.
     * @return A FinalValueNode with the given value.
     */
    private final ValueNode registerFinalValue(int value) {
        // We always register final values because while ADDING
        // we do not know yet whether we will build fast or small.
        lookupFinalValueNode.setFinalValue(value);
        Node oldNode = nodes.get(lookupFinalValueNode);
        if (oldNode != null) {
            return (ValueNode) oldNode;
        }
        ValueNode newNode = new ValueNode(value);
        // If put() returns a non-null value from an equivalent, previously
        // registered node, then get() failed to find that and we will leak newNode.
        oldNode = nodes.put(newNode, newNode);
        assert (oldNode == null);
        return newNode;
    }

    private abstract static class Node {
        public Node() {
            offset = 0;
        }

        // hashCode() and equals() for use with registerNode() and the nodes hash.
        @Override
        public abstract int hashCode() /*const*/;

        // Base class equals() compares the actual class types.
        @Override
        public boolean equals(Object other) {
            return this == other || this.getClass() == other.getClass();
        }

        /**
         * Recursive method for adding a new (string, value) pair. Matches the remaining part of s
         * from start, and adds a new node where there is a mismatch.
         *
         * @return this or a replacement Node
         */
        public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
            return this;
        }

        /**
         * Recursive method for registering unique nodes, after all (string, value) pairs have been
         * added. Final-value nodes are pre-registered while add()ing (string, value) pairs. Other
         * nodes created while add()ing registerNode() themselves later and might replace themselves
         * with new types of nodes for write()ing.
         *
         * @return The registered version of this node which implements write().
         */
        public Node register(StringTrieBuilder builder) {
            return this;
        }

        /**
         * Traverses the Node graph and numbers branch edges, with rightmost edges first. This is to
         * avoid writing a duplicate node twice.
         *
         * <p>Branch nodes in this trie data structure are not symmetric. Most branch edges "jump"
         * to other nodes but the rightmost branch edges just continue without a jump. Therefore,
         * write() must write the rightmost branch edge last (trie units are written backwards), and
         * must write it at that point even if it is a duplicate of a node previously written
         * elsewhere.
         *
         * <p>This function visits and marks right branch edges first. Edges are numbered with
         * increasingly negative values because we share the offset field which gets positive values
         * when nodes are written. A branch edge also remembers the first number for any of its
         * edges.
         *
         * <p>When a further-left branch edge has a number in the range of the rightmost edge's
         * numbers, then it will be written as part of the required right edge and we can avoid
         * writing it first.
         *
         * <p>After root.markRightEdgesFirst(-1) the offsets of all nodes are negative edge numbers.
         *
         * @param edgeNumber The first edge number for this node and its sub-nodes.
         * @return An edge number that is at least the maximum-negative of the input edge number and
         *     the numbers of this node and all of its sub-nodes.
         */
        public int markRightEdgesFirst(int edgeNumber) {
            if (offset == 0) {
                offset = edgeNumber;
            }
            return edgeNumber;
        }

        // write() must set the offset to a positive value.
        public abstract void write(StringTrieBuilder builder);

        // See markRightEdgesFirst.
        public final void writeUnlessInsideRightEdge(
                int firstRight, int lastRight, StringTrieBuilder builder) {
            // Note: Edge numbers are negative, lastRight<=firstRight.
            // If offset>0 then this node and its sub-nodes have been written already
            // and we need not write them again.
            // If this node is part of the unwritten right branch edge,
            // then we wait until that is written.
            if (offset < 0 && (offset < lastRight || firstRight < offset)) {
                write(builder);
            }
        }

        public final int getOffset() /*const*/ {
            return offset;
        }

        protected int offset;
    }

    // Used directly for final values, and as as a superclass for
    // match nodes with intermediate values.
    private static class ValueNode extends Node {
        public ValueNode() {}

        public ValueNode(int v) {
            hasValue = true;
            value = v;
        }

        public final void setValue(int v) {
            assert (!hasValue);
            hasValue = true;
            value = v;
        }

        private void setFinalValue(int v) {
            hasValue = true;
            value = v;
        }

        @Override
        public int hashCode() /*const*/ {
            int hash = 0x111111;
            if (hasValue) {
                hash = hash * 37 + value;
            }
            return hash;
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!super.equals(other)) {
                return false;
            }
            ValueNode o = (ValueNode) other;
            return hasValue == o.hasValue && (!hasValue || value == o.value);
        }

        @Override
        public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
            if (start == s.length()) {
                throw new IllegalArgumentException("Duplicate string.");
            }
            // Replace self with a node for the remaining string suffix and value.
            ValueNode node = builder.createSuffixNode(s, start, sValue);
            node.setValue(value);
            return node;
        }

        @Override
        public void write(StringTrieBuilder builder) {
            offset = builder.writeValueAndFinal(value, true);
        }

        protected boolean hasValue;
        protected int value;
    }

    private static final class IntermediateValueNode extends ValueNode {
        public IntermediateValueNode(int v, Node nextNode) {
            next = nextNode;
            setValue(v);
        }

        @Override
        public int hashCode() /*const*/ {
            return (0x222222 * 37 + value) * 37 + next.hashCode();
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!super.equals(other)) {
                return false;
            }
            IntermediateValueNode o = (IntermediateValueNode) other;
            return next == o.next;
        }

        @Override
        public int markRightEdgesFirst(int edgeNumber) {
            if (offset == 0) {
                offset = edgeNumber = next.markRightEdgesFirst(edgeNumber);
            }
            return edgeNumber;
        }

        @Override
        public void write(StringTrieBuilder builder) {
            next.write(builder);
            offset = builder.writeValueAndFinal(value, false);
        }

        private Node next;
    }

    private static final class LinearMatchNode extends ValueNode {
        public LinearMatchNode(CharSequence builderStrings, int sOffset, int len, Node nextNode) {
            strings = builderStrings;
            stringOffset = sOffset;
            length = len;
            next = nextNode;
        }

        @Override
        public int hashCode() /*const*/ {
            return hash;
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!super.equals(other)) {
                return false;
            }
            LinearMatchNode o = (LinearMatchNode) other;
            if (length != o.length || next != o.next) {
                return false;
            }
            for (int i = stringOffset, j = o.stringOffset, limit = stringOffset + length;
                    i < limit;
                    ++i, ++j) {
                if (strings.charAt(i) != strings.charAt(j)) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
            if (start == s.length()) {
                if (hasValue) {
                    throw new IllegalArgumentException("Duplicate string.");
                } else {
                    setValue(sValue);
                    return this;
                }
            }
            int limit = stringOffset + length;
            for (int i = stringOffset; i < limit; ++i, ++start) {
                if (start == s.length()) {
                    // s is a prefix with a new value. Split self into two linear-match nodes.
                    int prefixLength = i - stringOffset;
                    LinearMatchNode suffixNode =
                            new LinearMatchNode(strings, i, length - prefixLength, next);
                    suffixNode.setValue(sValue);
                    length = prefixLength;
                    next = suffixNode;
                    return this;
                }
                char thisChar = strings.charAt(i);
                char newChar = s.charAt(start);
                if (thisChar != newChar) {
                    // Mismatch, insert a branch node.
                    DynamicBranchNode branchNode = new DynamicBranchNode();
                    // Reuse this node for one of the remaining substrings, if any.
                    Node result, thisSuffixNode;
                    if (i == stringOffset) {
                        // Mismatch on first character, turn this node into a suffix.
                        if (hasValue) {
                            // Move the value for prefix length "start" to the new node.
                            branchNode.setValue(value);
                            value = 0;
                            hasValue = false;
                        }
                        ++stringOffset;
                        --length;
                        thisSuffixNode = length > 0 ? this : next;
                        // C++: if(length==0) { delete this; }
                        result = branchNode;
                    } else if (i == limit - 1) {
                        // Mismatch on last character, keep this node for the prefix.
                        --length;
                        thisSuffixNode = next;
                        next = branchNode;
                        result = this;
                    } else {
                        // Mismatch on intermediate character, keep this node for the prefix.
                        int prefixLength = i - stringOffset;
                        ++i; // Suffix start offset (after thisChar).
                        thisSuffixNode =
                                new LinearMatchNode(strings, i, length - (prefixLength + 1), next);
                        length = prefixLength;
                        next = branchNode;
                        result = this;
                    }
                    ValueNode newSuffixNode = builder.createSuffixNode(s, start + 1, sValue);
                    branchNode.add(thisChar, thisSuffixNode);
                    branchNode.add(newChar, newSuffixNode);
                    return result;
                }
            }
            // s matches all of this node's characters.
            next = next.add(builder, s, start, sValue);
            return this;
        }

        @Override
        public Node register(StringTrieBuilder builder) {
            next = next.register(builder);
            // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength.
            int maxLinearMatchLength = builder.getMaxLinearMatchLength();
            while (length > maxLinearMatchLength) {
                int nextOffset = stringOffset + length - maxLinearMatchLength;
                length -= maxLinearMatchLength;
                LinearMatchNode suffixNode =
                        new LinearMatchNode(strings, nextOffset, maxLinearMatchLength, next);
                suffixNode.setHashCode();
                next = builder.registerNode(suffixNode);
            }
            Node result;
            if (hasValue && !builder.matchNodesCanHaveValues()) {
                int intermediateValue = value;
                value = 0;
                hasValue = false;
                setHashCode();
                result = new IntermediateValueNode(intermediateValue, builder.registerNode(this));
            } else {
                setHashCode();
                result = this;
            }
            return builder.registerNode(result);
        }

        @Override
        public int markRightEdgesFirst(int edgeNumber) {
            if (offset == 0) {
                offset = edgeNumber = next.markRightEdgesFirst(edgeNumber);
            }
            return edgeNumber;
        }

        @Override
        public void write(StringTrieBuilder builder) {
            next.write(builder);
            builder.write(stringOffset, length);
            offset =
                    builder.writeValueAndType(
                            hasValue, value, builder.getMinLinearMatch() + length - 1);
        }

        // Must be called just before registerNode(this).
        private void setHashCode() /*const*/ {
            hash = (0x333333 * 37 + length) * 37 + next.hashCode();
            if (hasValue) {
                hash = hash * 37 + value;
            }
            for (int i = stringOffset, limit = stringOffset + length; i < limit; ++i) {
                hash = hash * 37 + strings.charAt(i);
            }
        }

        private CharSequence strings;
        private int stringOffset;
        private int length;
        private Node next;
        private int hash;
    }

    private static final class DynamicBranchNode extends ValueNode {
        public DynamicBranchNode() {}

        // c must not be in chars yet.
        public void add(char c, Node node) {
            int i = find(c);
            chars.insert(i, c);
            equal.add(i, node);
        }

        @Override
        public Node add(StringTrieBuilder builder, CharSequence s, int start, int sValue) {
            if (start == s.length()) {
                if (hasValue) {
                    throw new IllegalArgumentException("Duplicate string.");
                } else {
                    setValue(sValue);
                    return this;
                }
            }
            char c = s.charAt(start++);
            int i = find(c);
            if (i < chars.length() && c == chars.charAt(i)) {
                equal.set(i, equal.get(i).add(builder, s, start, sValue));
            } else {
                chars.insert(i, c);
                equal.add(i, builder.createSuffixNode(s, start, sValue));
            }
            return this;
        }

        @Override
        public Node register(StringTrieBuilder builder) {
            Node subNode = register(builder, 0, chars.length());
            BranchHeadNode head = new BranchHeadNode(chars.length(), subNode);
            Node result = head;
            if (hasValue) {
                if (builder.matchNodesCanHaveValues()) {
                    head.setValue(value);
                } else {
                    result = new IntermediateValueNode(value, builder.registerNode(head));
                }
            }
            return builder.registerNode(result);
        }

        private Node register(StringTrieBuilder builder, int start, int limit) {
            int length = limit - start;
            if (length > builder.getMaxBranchLinearSubNodeLength()) {
                // Branch on the middle unit.
                int middle = start + length / 2;
                return builder.registerNode(
                        new SplitBranchNode(
                                chars.charAt(middle),
                                register(builder, start, middle),
                                register(builder, middle, limit)));
            }
            ListBranchNode listNode = new ListBranchNode(length);
            do {
                char c = chars.charAt(start);
                Node node = equal.get(start);
                if (node.getClass() == ValueNode.class) {
                    // Final value.
                    listNode.add(c, ((ValueNode) node).value);
                } else {
                    listNode.add(c, node.register(builder));
                }
            } while (++start < limit);
            return builder.registerNode(listNode);
        }

        private int find(char c) {
            int start = 0;
            int limit = chars.length();
            while (start < limit) {
                int i = (start + limit) / 2;
                char middleChar = chars.charAt(i);
                if (c < middleChar) {
                    limit = i;
                } else if (c == middleChar) {
                    return i;
                } else {
                    start = i + 1;
                }
            }
            return start;
        }

        private StringBuilder chars = new StringBuilder();
        private ArrayList<Node> equal = new ArrayList<Node>();
    }

    private abstract static class BranchNode extends Node {
        public BranchNode() {}

        @Override
        public int hashCode() /*const*/ {
            return hash;
        }

        protected int hash;
        protected int firstEdgeNumber;
    }

    private static final class ListBranchNode extends BranchNode {
        public ListBranchNode(int capacity) {
            hash = 0x444444 * 37 + capacity;
            equal = new Node[capacity];
            values = new int[capacity];
            units = new char[capacity];
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!super.equals(other)) {
                return false;
            }
            ListBranchNode o = (ListBranchNode) other;
            for (int i = 0; i < length; ++i) {
                if (units[i] != o.units[i] || values[i] != o.values[i] || equal[i] != o.equal[i]) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public int markRightEdgesFirst(int edgeNumber) {
            if (offset == 0) {
                firstEdgeNumber = edgeNumber;
                int step = 0;
                int i = length;
                do {
                    Node edge = equal[--i];
                    if (edge != null) {
                        edgeNumber = edge.markRightEdgesFirst(edgeNumber - step);
                    }
                    // For all but the rightmost edge, decrement the edge number.
                    step = 1;
                } while (i > 0);
                offset = edgeNumber;
            }
            return edgeNumber;
        }

        @Override
        public void write(StringTrieBuilder builder) {
            // Write the sub-nodes in reverse order: The jump lengths are deltas from
            // after their own positions, so if we wrote the minUnit sub-node first,
            // then its jump delta would be larger.
            // Instead we write the minUnit sub-node last, for a shorter delta.
            int unitNumber = length - 1;
            Node rightEdge = equal[unitNumber];
            int rightEdgeNumber = rightEdge == null ? firstEdgeNumber : rightEdge.getOffset();
            do {
                --unitNumber;
                if (equal[unitNumber] != null) {
                    equal[unitNumber].writeUnlessInsideRightEdge(
                            firstEdgeNumber, rightEdgeNumber, builder);
                }
            } while (unitNumber > 0);
            // The maxUnit sub-node is written as the very last one because we do
            // not jump for it at all.
            unitNumber = length - 1;
            if (rightEdge == null) {
                builder.writeValueAndFinal(values[unitNumber], true);
            } else {
                rightEdge.write(builder);
            }
            offset = builder.write(units[unitNumber]);
            // Write the rest of this node's unit-value pairs.
            while (--unitNumber >= 0) {
                int value;
                boolean isFinal;
                if (equal[unitNumber] == null) {
                    // Write the final value for the one string ending with this unit.
                    value = values[unitNumber];
                    isFinal = true;
                } else {
                    // Write the delta to the start position of the sub-node.
                    assert (equal[unitNumber].getOffset() > 0);
                    value = offset - equal[unitNumber].getOffset();
                    isFinal = false;
                }
                builder.writeValueAndFinal(value, isFinal);
                offset = builder.write(units[unitNumber]);
            }
        }

        // Adds a unit with a final value.
        public void add(int c, int value) {
            units[length] = (char) c;
            equal[length] = null;
            values[length] = value;
            ++length;
            hash = (hash * 37 + c) * 37 + value;
        }

        // Adds a unit which leads to another match node.
        public void add(int c, Node node) {
            units[length] = (char) c;
            equal[length] = node;
            values[length] = 0;
            ++length;
            hash = (hash * 37 + c) * 37 + node.hashCode();
        }

        // Note: We could try to reduce memory allocations
        // by replacing these per-node arrays with per-builder ArrayLists and
        // (for units) a StringBuilder (or even use its strings for the units too).
        // It remains to be seen whether that would improve performance.
        private Node[] equal; // null means "has final value".
        private int length;
        private int[] values;
        private char[] units;
    }

    private static final class SplitBranchNode extends BranchNode {
        public SplitBranchNode(char middleUnit, Node lessThanNode, Node greaterOrEqualNode) {
            hash =
                    ((0x555555 * 37 + middleUnit) * 37 + lessThanNode.hashCode()) * 37
                            + greaterOrEqualNode.hashCode();
            unit = middleUnit;
            lessThan = lessThanNode;
            greaterOrEqual = greaterOrEqualNode;
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!super.equals(other)) {
                return false;
            }
            SplitBranchNode o = (SplitBranchNode) other;
            return unit == o.unit && lessThan == o.lessThan && greaterOrEqual == o.greaterOrEqual;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public int markRightEdgesFirst(int edgeNumber) {
            if (offset == 0) {
                firstEdgeNumber = edgeNumber;
                edgeNumber = greaterOrEqual.markRightEdgesFirst(edgeNumber);
                offset = edgeNumber = lessThan.markRightEdgesFirst(edgeNumber - 1);
            }
            return edgeNumber;
        }

        @Override
        public void write(StringTrieBuilder builder) {
            // Encode the less-than branch first.
            lessThan.writeUnlessInsideRightEdge(
                    firstEdgeNumber, greaterOrEqual.getOffset(), builder);
            // Encode the greater-or-equal branch last because we do not jump for it at all.
            greaterOrEqual.write(builder);
            // Write this node.
            assert (lessThan.getOffset() > 0);
            builder.writeDeltaTo(lessThan.getOffset()); // less-than
            offset = builder.write(unit);
        }

        private char unit;
        private Node lessThan;
        private Node greaterOrEqual;
    }

    // Branch head node, for writing the actual node lead unit.
    private static final class BranchHeadNode extends ValueNode {
        public BranchHeadNode(int len, Node subNode) {
            length = len;
            next = subNode;
        }

        @Override
        public int hashCode() /*const*/ {
            return (0x666666 * 37 + length) * 37 + next.hashCode();
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (!super.equals(other)) {
                return false;
            }
            BranchHeadNode o = (BranchHeadNode) other;
            return length == o.length && next == o.next;
        }

        @Override
        public int markRightEdgesFirst(int edgeNumber) {
            if (offset == 0) {
                offset = edgeNumber = next.markRightEdgesFirst(edgeNumber);
            }
            return edgeNumber;
        }

        @Override
        public void write(StringTrieBuilder builder) {
            next.write(builder);
            if (length <= builder.getMinLinearMatch()) {
                offset = builder.writeValueAndType(hasValue, value, length - 1);
            } else {
                builder.write(length - 1);
                offset = builder.writeValueAndType(hasValue, value, 0);
            }
        }

        private int length;
        private Node next; // A branch sub-node.
    }

    private ValueNode createSuffixNode(CharSequence s, int start, int sValue) {
        ValueNode node = registerFinalValue(sValue);
        if (start < s.length()) {
            int offset = strings.length();
            strings.append(s, start, s.length());
            node = new LinearMatchNode(strings, offset, s.length() - start, node);
        }
        return node;
    }

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract boolean matchNodesCanHaveValues() /*const*/;

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int getMaxBranchLinearSubNodeLength() /*const*/;

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int getMinLinearMatch() /*const*/;

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int getMaxLinearMatchLength() /*const*/;

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int write(int unit);

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int write(int offset, int length);

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int writeValueAndFinal(int i, boolean isFinal);

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int writeValueAndType(boolean hasValue, int value, int node);

    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated
    protected abstract int writeDeltaTo(int jumpTarget);

    private enum State {
        ADDING,
        BUILDING_FAST,
        BUILDING_SMALL,
        BUILT
    }

    private State state = State.ADDING;

    // Strings and sub-strings for linear-match nodes.
    /**
     * @internal
     * @deprecated This API is ICU internal only.
     */
    @Deprecated protected StringBuilder strings = new StringBuilder();

    private Node root;

    // Hash set of nodes, maps from nodes to integer 1.
    private HashMap<Node, Node> nodes = new HashMap<Node, Node>();
    private ValueNode lookupFinalValueNode = new ValueNode();
}
